//
// Created by LiuYou on 2021/5/25.
//

#include <cstdlib>
#include <set>
#include <string>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <iterator>

//#define DEBUG

/**
 * @brief 集合覆盖问题 这个程序编译是有问题的, 改进请看 SetCoverProblem02.cpp。
 */
int main() {
    // 8个
    std::set<std::string> statesNeeded({"mt", "wa", "or", "id", "nv", "ut", "ca", "az"});
//    std::set<std::string> statesNeeded({std::string("mt"), std::string("wa"), std::string("or"), std::string("id"),
//                                        std::string("nv"), std::string("ut"), std::string("ca"), std::string("az")});

#ifdef DEBUG
    std::cout << "statesNeeded: " << std::endl;
    for (const auto& item : statesNeeded) {
        std::cout << item << std::endl;
    }
    std::cout << std::endl;
#endif

    // 广播台
    std::__umap_hashtable<std::string, std::set<std::string> > stations;
    stations["kone"] = std::set<std::string>({"id", "nv", "ut"});
    stations["ktwo"] = std::set<std::string>({"wa", "id", "mt"});
    stations["kthree"] = std::set<std::string>({"or", "nv", "ca"});
    stations["kfour"] = std::set<std::string>({"nv", "ut"});
    stations["kfive"] = std::set<std::string>({"ca", "az"});

    // 最终选择的广播台
    using SetString = std::set<std::string>;
    SetString finalStations;

    // 算法:
    std::pair<std::string, SetString> bestStation;
    SetString statesCovered;

#ifdef DEBUG
    std::cout << "stations: " << std::endl;
    for (const auto& item : stations) {
        std::cout << item.first << " ";
        for (const auto& elem : item.second) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }
#endif

    for (auto& item : stations) {
        for (auto& setItem : item.second) {
//            (std::string) (setItem);
            // TODO 注意:
            //  这里不知道为什么会报错！
            //   error: no match for ‘operator<’ (operand types are ‘const char’ and ‘const std::__cxx11::basic_string<char>’)
            //   error: no match for ‘operator<’ (operand types are ‘const std::__cxx11::basic_string<char>’ and ‘const char’)
            //       { return *__it1 < *__it2; }
            //                ~~~~~~~^~~~~~~~
            std::set_intersection(statesNeeded.cbegin(), statesNeeded.cend(), setItem.cbegin(), setItem.cend(),
                                  std::ostream_iterator<std::string>(std::cout, " ")/*,*/
                    /*std::equal_to<std::string>(statesNeeded, setItem)*/);

        }
    }


    std::exit(0);
}